package leetcode;

/**
 * @author caifangyi
 * @date 2022/9/5
 */

import java.util.*;

/**
 * 652. 寻找重复的子树
 * 
 * 给定一棵二叉树 root，返回所有重复的子树。
 *
 * 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 *
 * 如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
 *
 * 
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [1,2,3,4,null,2,4,null,null,4]
 * 输出：[[2,4],[4]]
 * 示例 2：
 *
 *
 *
 * 输入：root = [2,1,1]
 * 输出：[[1]]
 * 示例 3：
 *
 *
 *
 * 输入：root = [2,2,2,3,null,3,null]
 * 输出：[[2,3],[3]]
 * 
 *
 * 提示：
 *
 * 树中的结点数在[1,10^4]范围内。
 * -200 <= Node.val <= 200
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-duplicate-subtrees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Day0652 {

    public static void main(String[] args) {

    }

    /**
     * Definition for a binary tree node.
     *
     **/
     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }

    class Solution {
        public Map<String, TreeNode> map = new HashMap<>();
        public Set<TreeNode> repeats = new HashSet<>();

        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {

            //先进行二叉树的序列化，然后找出重复的部分
            dfs(root);
            return new ArrayList<>(repeats);
        }

        private String dfs(TreeNode root) {

            if(root == null){
                return "";
            }

            StringBuilder sb = new StringBuilder();
            sb.append(root.val);
            sb.append("(");
            sb.append(dfs(root.left));
            sb.append(")");
            sb.append("(");
            sb.append(dfs(root.right));
            sb.append(")");

            String key = sb.toString();

            if(map.containsKey(key)){
                repeats.add(map.get(key));
            }else{
                map.put(key, root);
            }
            return key;
        }
    }
}
